An important practical problem in automated inspection systems is a classification, categorization, or identification of an object. Generally, an automated inspection system classifies objects based on measurements taken of the object being inspected. Related to this problem is the challenge of identifying an object based on measurements taken from an image of the object. The latter of these is a problem common to both inspection systems and more general-purpose image processing systems. In simple terms, the objective or goal of the classification task performed by such systems is to use the measurements and/or combinations of the measurements of the object to determine the object's membership in one or more possible groups or classes of objects. For example, in a manufacturing inspection system, a customary goal is to determine whether a given object of manufacture is either ‘good’ or ‘bad’ (i.e. belongs to a class of good objects or a class of bad objects). Typically, measurements of the inspected object are compared either to measurements taken of known good and bad objects or to specifications defining good and bad objects and a determination of class membership (good or bad) is made.
Unfortunately, due to statistical variations in measured characteristics of the inspected objects and/or statistical errors in the measurements themselves, the determination of class membership usually is not deterministic but instead is made according to probability theory. In other words, the determination establishes a likelihood or probability that a given object is a member of a particular class or category. Moreover, in many practical cases no single measurement can be used to reliably perform the categorization. Instead, multiple measurements are often required. The measurements and/or combinations of the measurements can be thought of as ‘features’ of the object. The object features are compared to sets of representative features for each of the possible groups and a determination is made based on an aggregate of the comparison results. Thus, the classification problem is more correctly termed an estimation problem in which the probability of membership of the object in a particular group or class is estimated based on the features of the object. The branch of statistics that deals with the problem of classifying or estimating class membership based on features derived from multiple measurements is known as multivariate analysis or multivariate estimation.
For example, consider the automatic inspection of solder joints using an imaging system such as an X-ray laminography system. The laminography system produces images of the solder joints on a printed circuit board (PCB) being inspected. A computer then processes the images and attempts to determine if the solder joints are ‘good joints’ or ‘bad joints’. The goal is to correctly detect bad solder joints so that they can be flagged and not end up in a finished PCB. A simultaneous goal to that of detecting bad joints is to avoid incorrectly labeling good joints as bad joints since this would cause unwarranted increases in printed circuit board (PCB) production costs.
The classification process in such inspection systems is often based on features extracted from images of the solder joints. The features of each solder joint typically number in the tens of features per solder joint inspected and include, but are not limited to, such things as the estimated volume of solder in a heel of the joint and estimated volume of solder in a toe of the joint. Since experience has shown that no single measurement or feature correlates sufficiently well with whether a solder joint is good or bad, it is necessary to consider a number of features as an aggregate to distinguish good joints from bad joints. It is hoped that if a solder joint is bad, it will clearly fail or be classified as bad for at least one feature.
As discussed above, the analysis and decision-making is complicated by the necessity of using multiple features in the solder joint classification. In general, dividing lines between statistical distributions of features representing good and bad joints are drawn liberally, favoring type II errors, over type I errors. In type II errors, a bad joint is erroneously classified as a good joint while with type I errors, a good joint is erroneously classified as a bad joint. Thus, for a solder joint to be categorized as a bad joint, a typical criterion is that the solder joint must clearly fail with respect to at least one of the measurements or features. Fuzzy logic and expert systems approaches additionally can allow for the possibility of flagging a bad solder joint because several features may show it to be questionable. Even with such techniques, only an examination of the multivariate statistical distribution will reveal a structure of the distribution with sufficient diagnostic power to make a reliable class membership determination.
The general problem of estimating a multivariate probability density function of a set of features representing an object or class of objects is at best difficult and becomes more problematic as the number of dimensions (i.e., variables or features) increases. As the number of dimensions increases, the volume of the feature space increases exponentially. Increases in feature space volume make it increasingly difficult to estimate the local probability density, especially based on a limited sample population of objects with known class membership. In practice, there are often insufficient sample points nearby to a given location in the measurement space with which to make a reliable local estimate. Another way to look at the situation is that the number of parameters required to specify an arbitrary multivariate distribution rises exponentially with dimensionality.
Often the problem of estimating the probability density function can be made more tractable by modeling the density function as a mixture or combination of one or more relatively simple distribution functions. For example, one of the simplest, and consequently mostly widely used, multivariate distributions is the multivariate Gaussian. However, even with the use of one or more simple distribution functions, the number of parameters can still be a concern. The multivariate Gaussian, for instance, contains n(n+3)/2 parameters, where n is the dimensionality of the feature space. While the increase in feature space dimensionality for the Gaussian is less than exponential, there still would be 350 parameters required for a single Gaussian of dimensionality n=25. In turn, each class (e.g. good and bad) generally needs at least as many samples as there are parameters, and in most cases, many times more samples to make a reliable estimate. Moreover, since bad components are generally rare, it can be difficult to obtain a large representative sample set that adequately encompasses the probable failure modes. Furthermore, correlations among the measurements that contain errors can and do cause the estimation process to be computationally ill-conditioned. Ill-conditioning leads to errors in the estimation and in the worst cases, complete failure of the estimation process.
Accordingly, it would be advantageous to have a method for classifying unknown objects as being a member of a class, where the method utilizes multiple features derived from measurements of known objects to define classes. Furthermore, it would desirable for such a method to employ an approach for reducing the dimensionality of the feature space that preserves the important or significant features, and by extension, the diagnostic power of the feature space. Such a method would solve a long-standing need in the area of multivariate estimation as it is used in image processing and automated inspection.